Grokking Tree Coding Patterns for Interviews
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Course Overview
Introduction to Tree
Types of Tree
BST Traversal Techniques
BST Operations
Introduction to Level Order Traversal Pattern
Reverse Level Order Traversal (easy)
Solution: Reverse Level Order Traversal
Find Largest Value in Each Tree Row (medium)
Solution: Find Largest Value in Each Tree Row
Maximum Width of Binary Tree (medium)
Solution: Maximum Width of Binary Tree
Maximum Level Sum of a Binary Tree (medium)
Solution: Maximum Level Sum of a Binary Tree
Zigzag Traversal (medium)
Solution: Zigzag Traversal
Even Odd Tree (medium)
Solution: Even Odd Tree
N-ary Tree Level Order Traversal (hard)
Solution: N-ary Tree Level Order Traversal
Introduction to Tree Depth Pattern
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Balanced Binary Tree (easy)
Solution: Balanced Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Maximum Depth of N-ary Tree (easy)
Solution: Maximum Depth of N-ary Tree
Find maximum depth of subtree (medium)
Solution: Find maximum depth of subtree
Root to Leaf Path Pattern (medium)
Introduction to Root to Leaf Path Pattern
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Sum of Root To Leaf Binary Numbers (easy)
Solution: Sum of Root To Leaf Binary Numbers
Insufficient Nodes in Root to Leaf Paths (medium)
Solution: Insufficient Nodes in Root to Leaf Paths
Smallest String Starting From Leaf (medium)
Solution: Smallest String Starting From Leaf
Pseudo-Palindromic Paths in a Binary Tree (medium)
Solution: Pseudo-Palindromic Paths in a Binary Tree
All Paths for a Sum (medium)
Solution: All Paths for a Sum
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Path With Given Sequence (medium)
Solution: Path With Given Sequence
Count Paths for a Sum (medium)
Solution: Count Paths for a Sum
Leaf Processing Pattern (medium)
Introduction to Leaf Processing Pattern
Sum of Left Leaves (easy)
Solution: Sum of Left Leaves
Leaf-Similar Trees (easy)
Solution: Leaf-Similar Trees
Check if all leaves are at same level (medium)
Solution: Check if all leaves are at same level
Delete Leaves With a Given Value (medium)
Solution: Delete Leaves With a Given Value
Deepest Leaves Sum (medium)
Solution: Deepest Leaves Sum
Tree View Pattern (medium)
Introduction to Tree View Pattern
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Top View Of the Binary Tree (medium)
Solution: Top View Of the Binary Tree
Bottom View Of the Binary Tree (medium)
Solution: Bottom View Of the Binary Tree
Boundary of Binary Tree (medium)
Solution: Boundary of Binary Tree
Introduction to Comparison of Two Trees Pattern
Symmetric Tree (easy)
Solution: Symmetric Tree
Mirror Image Trees (medium)
Solution: Mirror Image Trees
Subtree of Another Tree (easy)
Solution: Subtree of Another Tree
Isomorphic Trees (medium)
Solution: Isomorphic Trees
Introduction to Serialize and Deserialize Tree Pattern
Serialize and Deserialize BST (medium)
Solution: Serialize and Deserialize BST
Verify Preorder Serialization of a Binary Tree (medium)
Solution: Verify Preorder Serialization of a Binary Tree
Create Binary Tree From Descriptions (medium)
Solution: Create Binary Tree From Descriptions
Serialize and Deserialize N-ary Tree (hard)
Solution: Serialize and Deserialize N-ary Tree
Solution: Top View Of the Binary Tree

Problem Statement

Given a root of the binary tree, return an array containing nodes in its top view.

The top view of a binary tree consists of nodes that are visible when the tree is viewed from the top. If multiple nodes share the same horizontal distance from the root, only the first node encountered at that distance (in level order) is part of the top view.

Examples

Example 1

  • Input: root = [1, 2, 3, null, 5, 4, 6]
  • Expected Output: [2, 1, 3, 6]
Image
  • Justification: It is a top view of the tree as shown in the diagram.

Example 2

  • Input: root = [1, 2, 3, 4, null, null, 7, 5, null, null, 8]
  • Expected Output: [5, 4, 2, 1, 3, 7, 8]
Image
  • Justification: It is a top view of the tree as shown in the diagram.

Example 3

  • Input: root = [1, null, 2, 3, null, null, 4]
  • Expected Output: [1, 2]
Image
  • Justification: It is a top view of the tree as shown in the diagram.

Solution

To solve this problem, we can use the Breadth-First Search (BFS) approach. This method explores each level of the tree and ensures that the first node encountered at each horizontal distance is captured. We maintain a horizontal distance for each node starting from the root (horizontal distance = 0) and update the view with the first node encountered at each distance.

This approach is efficient because BFS ensures that we process nodes level by level, and we can keep track of horizontal distances using a queue. Since we're only interested in the first node we encounter at each horizontal distance, BFS works perfectly for this case. We also maintain a hash map to store the top view nodes for each horizontal distance.

Step-by-step Algorithm

  1. Check if the tree is empty:

    • If the root is null, return an empty list since no top view is possible.
  2. Create necessary data structures:

    • Initialize an empty list topViewNodes to store the result.
    • Use a TreeMap called topNodeMap to store the first node encountered at each horizontal distance. The key is the horizontal distance, and the value is the node value.
    • Use a Queue to perform Breadth-First Search (BFS). The queue will store pairs of nodes and their respective horizontal distance from the root.
  3. Add the root node to the queue:

    • Insert the root node into the queue with a horizontal distance of 0.
  4. Start BFS traversal:

    • While the queue is not empty, repeat steps 5 to 9:
  5. Dequeue a node from the queue:

    • Remove a node from the queue along with its horizontal distance.
  6. Check if the horizontal distance is already in the map:

    • If this horizontal distance is not in topNodeMap, insert the current node’s value into the map with its horizontal distance as the key.
    • This ensures only the first node encountered at this horizontal distance is stored, as we are processing the tree level by level.
  7. Check if the current node has a left child:

    • If the node has a left child, enqueue the left child with a horizontal distance of current horizontal distance - 1.
  8. Check if the current node has a right child:

    • If the node has a right child, enqueue the right child with a horizontal distance of current horizontal distance + 1.
  9. Repeat the BFS traversal for all nodes:

    • Continue until all nodes are processed in the BFS loop.
  10. Extract the results:

    • After the BFS completes, the topNodeMap contains the first node encountered at each horizontal distance. Since TreeMap stores the keys in sorted order, iterate through the entries in topNodeMap and add the node values to topViewNodes.
  11. Return the result:

    • Return the list topViewNodes containing the top view of the binary tree.

Algorithm Walkthrough

Input: [1, 2, 3, null, 5, 4, 6]

Image
  1. Initial Setup:

    • topViewNodes = [] (empty list).
    • topNodeMap = {} (empty TreeMap).
    • queue = [(1, 0)] (root node 1 with horizontal distance 0).
  2. First BFS iteration:

    • Dequeue (1, 0): current node is 1, horizontal distance is 0.
    • Since horizontal distance 0 is not in topNodeMap, add 1 to the map: topNodeMap = {0: 1}.
    • Enqueue the left child 2 with horizontal distance -1: queue = [(2, -1)].
    • Enqueue the right child 3 with horizontal distance 1: queue = [(2, -1), (3, 1)].
  3. Second BFS iteration:

    • Dequeue (2, -1): current node is 2, horizontal distance is -1.
    • Since horizontal distance -1 is not in topNodeMap, add 2 to the map: topNodeMap = {-1: 2, 0: 1}.
    • Node 2 has no left child, so nothing is enqueued.
    • Enqueue the right child 5 with horizontal distance 0: queue = [(3, 1), (5, 0)].
  4. Third BFS iteration:

    • Dequeue (3, 1): current node is 3, horizontal distance is 1.
    • Since horizontal distance 1 is not in topNodeMap, add 3 to the map: topNodeMap = {-1: 2, 0: 1, 1: 3}.
    • Enqueue the left child 4 with horizontal distance 0: queue = [(5, 0), (4, 0)].
    • Enqueue the right child 6 with horizontal distance 2: queue = [(5, 0), (4, 0), (6, 2)].
  5. Fourth BFS iteration:

    • Dequeue (5, 0): current node is 5, horizontal distance is 0.
    • Since horizontal distance 0 is already in topNodeMap, we do not update the map (only the first node at each distance is kept).
    • Node 5 has no children, so nothing is enqueued.
  6. Fifth BFS iteration:

    • Dequeue (4, 0): current node is 4, horizontal distance is 0.
    • Since horizontal distance 0 is already in topNodeMap, we do not update the map.
    • Node 4 has no children, so nothing is enqueued.
  7. Sixth BFS iteration:

    • Dequeue (6, 2): current node is 6, horizontal distance is 2.
    • Since horizontal distance 2 is not in topNodeMap, add 6 to the map: topNodeMap = {-1: 2, 0: 1, 1: 3, 2: 6}.
    • Node 6 has no children, so nothing is enqueued.
  8. BFS completed:

    • The queue is now empty, so we exit the BFS loop.
  9. Extract the results:

    • Iterate through topNodeMap in order of horizontal distance: -1, 0, 1, 2.
    • Add the corresponding node values to topViewNodes: [2, 1, 3, 6].
  10. Return the result:

  • The final result is topViewNodes = [2, 1, 3, 6].

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

1. Level Order Traversal using Queue – :

  • Every node in the tree is visited exactly once during the Breadth-First Search (BFS).
  • For each node, we perform a constant amount of work (checking left/right children, calculating horizontal distance, etc.).
  • So this part contributes

2. Storing values in TreeMap – per insertion:

  • A TreeMap is used to keep nodes sorted by horizontal distance.
  • Each put() or containsKey() operation in a TreeMap takes , where K is the number of keys in the map.
  • In the worst case, you could have up to N different horizontal distances → so each insertion/check could take up to time.
  • Over N nodes, the map operations cost in total.

3. Collecting and returning results – :

  • After BFS, you collect values from the TreeMap, which takes .

Final Time Complexity:

  • Queue traversal (BFS):
  • TreeMap operations:
  • Final result construction:

✅ So the overall time complexity is due to the use of TreeMap for sorting horizontal distances.

Space Complexity

  • The space complexity of the algorithm is . This includes:
    • The queue used for BFS traversal, which in the worst case can contain nodes.
    • The TreeMap that stores nodes at different horizontal distances. In the worst case, the tree can be completely skewed, which means the number of unique horizontal distances will also be .
Top View Of the Binary Tree (medium)
Bottom View Of the Binary Tree (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity